home *** CD-ROM | disk | FTP | other *** search
/ Danny Amor's Online Library / Danny Amor's Online Library - Volume 1.iso / bbs / rfc / rfcxxxx_8.lha / rfc1765 < prev    next >
Text File  |  1995-07-26  |  22KB  |  508 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                             J. Moy
  8. Request for Comments: 1765                                       Cascade
  9. Category: Experimental                                        March 1995
  10.  
  11.  
  12.                          OSPF Database Overflow
  13.  
  14. Status of this Memo
  15.  
  16.    This memo defines an Experimental Protocol for the Internet
  17.    community.  This memo does not specify an Internet standard of any
  18.    kind.  Discussion and suggestions for improvement are requested.
  19.    Distribution of this memo is unlimited.
  20.  
  21. Abstract
  22.  
  23.    Proper operation of the OSPF protocol requires that all OSPF routers
  24.    maintain an identical copy of the OSPF link-state database.  However,
  25.    when the size of the link-state database becomes very large, some
  26.    routers may be unable to keep the entire database due to resource
  27.    shortages; we term this "database overflow". When database overflow
  28.    is anticipated, the routers with limited resources can be
  29.    accommodated by configuring OSPF stub areas and NSSAs. This memo
  30.    details a way of gracefully handling unanticipated database
  31.    overflows.
  32.  
  33.    This memo is a product of the OSPF Working Group. Please send
  34.    comments to ospf@gated.cornell.edu.
  35.  
  36. Table of Contents
  37.  
  38.    1.       Overview ............................................... 2
  39.    2.       Implementation details ................................. 3
  40.    2.1      Configuration .......................................... 3
  41.    2.2      Entering OverflowState ................................. 4
  42.    2.3      Operation while in OverflowState ....................... 5
  43.    2.3.1    Modifications to Flooding .............................. 5
  44.    2.3.2    Originating AS-external-LSAs ........................... 6
  45.    2.3.3    Receiving self-originated LSAs ......................... 6
  46.    2.4      Leaving OverflowState .................................. 6
  47.    3.       An example ............................................. 6
  48.    4.       Administrative response to database overflow ........... 7
  49.    5.       Operational experience ................................. 8
  50.    6.       Possible enhancements .................................. 8
  51.    A.       Related MIB parameters ................................  8
  52.             References ............................................  9
  53.             Security Considerations ...............................  9
  54.             Author's Address ......................................  9
  55.  
  56.  
  57.  
  58. Moy                                                             [Page 1]
  59.  
  60. RFC 1765                 OSPF Database Overflow               March 1995
  61.  
  62.  
  63. 1.  Overview
  64.  
  65.    OSPF requires that all OSPF routers within a single area maintain an
  66.    identical copy of the OSPF link-state database.  However, when the
  67.    size of the link-state database becomes very large, some routers may
  68.    be unable to keep the entire database due to resource shortages; we
  69.    term this "database overflow". For example, a regional network may
  70.    have a very large OSPF database because it is importing a large
  71.    number of external routes into OSPF. Unless database overflow is
  72.    handled correctly, routers will end up with inconsistent views of the
  73.    network, possibly leading to incorrect routing.
  74.  
  75.    One way of handling database overflow is to encase routers having
  76.    limited resources within OSPF stub areas (see Section 3.6 of [1]) or
  77.    NSSAs ([2]).  AS-external-LSAs are omitted from these areas' link-
  78.    state databases, thereby controlling database size.
  79.  
  80.    However, unexpected database overflows cannot be handled in the above
  81.    manner.  This memo describes a way of dynamically limiting database
  82.    size under overflow conditions. The basic mechanism is as follows:
  83.  
  84.     (1) A parameter, ospfExtLsdbLimit, is configured in each router
  85.         indicating the maximum number of AS-external-LSAs (excluding
  86.         those describing the default route) that are allowed in the
  87.         link-state database. This parameter must be the same in all
  88.         routers in the routing domain (see Section 2.1); synchronization
  89.         of the parameter is achieved via network management.
  90.  
  91.     (2) In any router's database, the number of AS-external-LSAs
  92.         (excluding default) is never allowed to exceed ospfExtLsdbLimit.
  93.         If a router receives a non-default AS-external-LSA that would
  94.         cause the limit of ospfExtLsdbLimit to be exceeded, it drops the
  95.         LSA and does NOT acknowledge it.
  96.  
  97.     (3) If the number of non-default AS-external-LSAs in a router's
  98.         database hits ospfExtLsdbLimit, the router a) flushes all non-
  99.         default AS-external-LSAs that it has itself originated (see
  100.         Section 2.2) and b) goes into "OverflowState".
  101.  
  102.     (4) While in OverflowState, the router refuses to originate any
  103.         non-default AS-external-LSAs (see Section 2.3.2).
  104.  
  105.     (5) Optionally, the router can attempt to leave OverflowState after
  106.         the configurable parameter ospfExitOverflowInterval has elapsed
  107.         since entering OverflowState (see Section 2.4). Only at this
  108.         point can the router resume originating non-default AS-
  109.         external-LSAs.
  110.  
  111.  
  112.  
  113.  
  114. Moy                                                             [Page 2]
  115.  
  116. RFC 1765                 OSPF Database Overflow               March 1995
  117.  
  118.  
  119.    The reason for limiting non-default AS-external-LSAs, but not other
  120.    LSA types, is twofold. First of all, the non-default AS-external LSAs
  121.    are the most likely to dominate database size in those networks with
  122.    huge databases (e.g., regional networks; see [5]). Second, the non-
  123.    default AS-external-LSAs can be viewed as "optional" in the following
  124.    sense: the router can probably be monitored/reconfigured without
  125.    them. (However, using similar strategies, other LSA types can also be
  126.    limited; see Section 5.)
  127.  
  128.    The method of dealing with database overflow described herein has the
  129.    following desirable properties:
  130.  
  131.     o   After a short period of convergence, all routers will have
  132.         identical link-state databases. This database will contain less
  133.         than ospfExtLsdbLimit non-default AS-external-LSAs.
  134.  
  135.     o   At all times, routing WITHIN the OSPF Autonomous System will
  136.         remain intact. Among other things, this means that the routers
  137.         will continue to be manageable.
  138.  
  139.     o   Default routing to external destinations will also remain
  140.         intact. This hopefully will mean that a large amount of external
  141.         connectivity will be preserved, although possibly taking less
  142.         efficient routes.
  143.  
  144.     o   If parameter ospfExitOverflowInterval is configured, the OSPF
  145.         system will recover fully and automatically (i.e., without
  146.         network management intervention) from transient database
  147.         overflow conditions (see Section 2.4).
  148.  
  149. 2.  Implementation details
  150.  
  151.    This section describes the mechanism for dealing with database
  152.    overflow in more detail. The section is organized around the concept
  153.    OverflowState, describing how routers enter the OverflowState, the
  154.    operation of the router while in OverflowState, and when the router
  155.    leaves OverflowState.
  156.  
  157.    2.1.  Configuration
  158.  
  159.       The following configuration parameters are added to support the
  160.       database overflow functionality. These parameters are set by
  161.       network management.
  162.  
  163.         ospfExtLsdbLimit
  164.             When the number of non-default AS-external-LSAs in a
  165.             router's link-state database reaches ospfExtLsdbLimit, the
  166.             router enters OverflowState. The router never holds more
  167.  
  168.  
  169.  
  170. Moy                                                             [Page 3]
  171.  
  172. RFC 1765                 OSPF Database Overflow               March 1995
  173.  
  174.  
  175.             than ospfExtLsdbLimit non-default AS-external-LSAs in its
  176.             database.
  177.  
  178.             ospfExtLsdbLimit MUST be set identically in all routers
  179.             attached to the OSPF backbone and/or any "regular" OSPF
  180.             area. (This memo does not pertain to routers contained
  181.             within OSPF stub areas nor NSSAs, since such routers do not
  182.             receive AS-external-LSAs.) If ospfExtLsdbLimit is not set
  183.             identically in all routers, then when the database
  184.             overflows: 1) the routers will NOT converge on a common
  185.             link-state database, 2) incorrect routing, possibly
  186.             including routing loops, will result and 3) constant
  187.             retransmission of AS-external-LSAs will occur. Identical
  188.             setting of ospfExtLsdbLimit is achieved/ensured by network
  189.             management.
  190.  
  191.             When ospfExtLsdbLimit is set in a router, the router must
  192.             have some way to guarantee that it can hold that many non-
  193.             default AS-external-LSAs in its link-state database. One way
  194.             of doing this is to preallocate resources (e.g., memory) for
  195.             the configured number of LSAs.
  196.  
  197.         ospfExitOverflowInterval
  198.             The number of seconds that, after entering OverflowState, a
  199.             router will attempt to leave OverflowState. This allows the
  200.             router to again originate non-default AS-external-LSAs. When
  201.             set to 0, the router will not leave OverflowState until
  202.             restarted. The default setting for ospfExitOverflowInterval
  203.             is 0.
  204.  
  205.             It is not necessary for ospfExitOverflowInterval to be
  206.             configured the same in all routers. A smaller value may be
  207.             configured in those routers that originate the "more
  208.             important" AS-external-LSAs. In fact, setting
  209.             ospfExitOverflowInterval the same may cause problems, as
  210.             multiple routers attempt to leave OverflowState
  211.             simultaneously. For this reason, the value of
  212.             ospfExitOverflowInterval must be "jittered" by randomly
  213.             varying its value within the range of plus or minus 10
  214.             percent before using.
  215.  
  216.    2.2.  Entering OverflowState
  217.  
  218.       The router enters OverflowState when the number of non-default
  219.       AS-external-LSAs in the database hits ospfExtLsdbLimit. There are
  220.       two cases when this can occur. First, when receiving an LSA during
  221.       flooding. In this case, an LSA which does not already have a
  222.       database instance is added in Step 5 of Section 13 of [1].  The
  223.  
  224.  
  225.  
  226. Moy                                                             [Page 4]
  227.  
  228. RFC 1765                 OSPF Database Overflow               March 1995
  229.  
  230.  
  231.       second case is when the router originates a non-default AS-
  232.       external-LSA itself.
  233.  
  234.       Whenever the router enters OverflowState it flushes all non-
  235.       default AS-external-LSAs that it itself had originated. Flushing
  236.       is accomplished through the premature aging scheme described in
  237.       Section 14.1 of [1].  Only self-originated LSAs are flushed; those
  238.       originated by other routers are kept in the link-state database.
  239.  
  240.    2.3.  Operation while in OverflowState
  241.  
  242.       While in OverflowState, the flooding and origination of non-
  243.       default AS-external-LSAs are modified in the following fashion.
  244.  
  245.       2.3.1.  Modifications to Flooding
  246.  
  247.          Flooding while in OverflowState is modified as follows. If in
  248.          Step 5 of Section 13 of [1], a non-default AS-external-LSA has
  249.          been received that a) has no current database instance and b)
  250.          would cause the count of non-default AS-external-LSAs to exceed
  251.          ospfExtLsdbLimit, then that LSA is discarded. Such an LSA is
  252.          not installed in the link-state database, nor is it
  253.          acknowledged.
  254.  
  255.          When all routers have identical values for ospfExtLsdbLimit (as
  256.          required), the above flooding modification will only be invoked
  257.          during a short period of convergence. During convergence, there
  258.          will be retransmissions of LSAs. However, after convergence the
  259.          retransmissions will cease, as the routers settle on a database
  260.          having less than ospfExtLsdbLimit non-default As-external-LSAs.
  261.  
  262.          In OverflowState, non-default AS-external-LSAs ARE still
  263.          accepted in the following conditions:
  264.  
  265.             (1) If the LSA updates an LSA that currently exists in the
  266.                 router's link-state database.
  267.  
  268.             (2) LSAs having LS age of MaxAge are always accepted. The
  269.                 processing of these LSAs follows the procedures
  270.                 described in Sections 13 and 14 of [1].
  271.  
  272.             (3) If adding the LSA to the router's database would keep
  273.                 the number of non-default AS-external-LSAs less than or
  274.                 equal to ospfExtLsdbLimit, the LSA is accepted.
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282. Moy                                                             [Page 5]
  283.  
  284. RFC 1765                 OSPF Database Overflow               March 1995
  285.  
  286.  
  287.       2.3.2.  Originating AS-external-LSAs
  288.  
  289.          Originating AS-external-LSAs is described in Section 12.4.5 of
  290.          [1].  When a router is in OverflowState, it does not originate
  291.          non-default AS-external-LSAs. In other words, the only AS-
  292.          external-LSAs originated by a router in OverflowState have Link
  293.          State ID 0.0.0.0.
  294.  
  295.       2.3.3.  Receiving self-originated LSAs
  296.  
  297.          Receiving self-originated LSAs is described in Section 13.4 of
  298.          [1].  When in OverflowState, a router receiving a self-
  299.          originated non-default AS-external-LSA responds by flushing it
  300.          from the routing domain using the premature aging scheme
  301.          described in Section 14.1 of [1].
  302.  
  303.    2.4.  Leaving OverflowState
  304.  
  305.       If ospfExitOverflowInterval is non-zero, then as soon as a router
  306.       enters OverflowState, it sets a timer equal to the value of
  307.       ospfExitOverflowInterval (plus or minus a random value in the
  308.       range of 10 percent). When this timer fires, the router leaves
  309.       OverflowState and begins originating non-default AS-external-LSAs
  310.       again.
  311.  
  312.       This allows a router to automatically recover from transient
  313.       overflow conditions. For example, an AS boundary router that
  314.       imports a great many AS-external-LSAs may crash. Other routers may
  315.       then start importing the routes, but until the crashed AS boundary
  316.       router is either a) restarted or b) its AS-external-LSAs age out,
  317.       there will be a much larger database than usual.  Since such an
  318.       overflow is guaranteed to go away in MaxAge seconds (1 hour),
  319.       automatic recovery may be appropriate (and fast enough) if the
  320.       overflow happens off-hours.
  321.  
  322.       As soon as the router leaves OverflowState, it is again eligible
  323.       to reenter OverflowState according to the text of Section 2.2.
  324.  
  325. 3.  An example
  326.  
  327.    As an example, suppose that a router implements the database overflow
  328.    logic, and that its ospfExtLsdbLimit is 10,000 and its
  329.    ospfExitOverflowInterval is set to 600 seconds. Suppose further that
  330.    the router itself is originating 400 non-default AS-external-LSAs,
  331.    and that the current number of non-default AS-external-LSAs in the
  332.    router's database is equal to 9,997.
  333.  
  334.  
  335.  
  336.  
  337.  
  338. Moy                                                             [Page 6]
  339.  
  340. RFC 1765                 OSPF Database Overflow               March 1995
  341.  
  342.  
  343.    Next, it receives a Link State Update packet from a neighbor,
  344.    containing 6 non-default AS-external-LSAs, none of which have current
  345.    database copies.  The first two LSAs are then installed in the
  346.    database. The third LSA is also installed in the database, but causes
  347.    the router to go into OverflowState.  Going into OverflowState causes
  348.    the router to flush (via premature aging) its 400 self-originated
  349.    non-default LSAs. However, these 400 LSAs are still considered to be
  350.    part of the link-state database until their re-flooding (with age set
  351.    to MaxAge) is acknowledged (see Section 14 of [1]); for this reason,
  352.    the last three LSAs in the received update are discarded without
  353.    being acknowledged.
  354.  
  355.    After some small period of time all routers will converge on a common
  356.    database, having less than 10,000 non-default AS-external-LSAs.
  357.    During this convergence period there may be some link-state
  358.    retransmissions; for example, the sender of the above Link State
  359.    Update packet may retransmit the three LSAs that were discarded. If
  360.    this retransmission happens after the flushing of the 400 self-
  361.    originated LSAs is acknowledged, the 3 LSAs will then be accepted.
  362.  
  363.    Going into OverflowState also causes the router to set a timer that
  364.    will fire some time between 540 and 660 seconds later. When this
  365.    timer fires, the router will leave OverflowState and re-originate its
  366.    400 non-default AS-external-LSAs, provided that the current database
  367.    has less than 9600 (10,000 - 400) non-default AS-external-LSAs. If
  368.    there are more than 9600, the timer is simply restarted.
  369.  
  370. 4.  Administrative response to database overflow
  371.  
  372.    Once the link-state database has overflowed, it may take intervention
  373.    by network management before all routing is restored.  (If the
  374.    overflow condition is transient, routing may be restored
  375.    automatically; see Section 2.4 for details.) An overflow condition is
  376.    indicated by SNMP traps (see Appendix B). Possible responses by a
  377.    network manager may include:
  378.  
  379.     o   Increasing the value of ospfExtLsdbLimit. Perhaps it had been
  380.         set too conservatively, and the routers are able to support
  381.         larger databases than they are currently configured for.
  382.  
  383.     o   Isolating routers having limited resources within OSPF stub
  384.         areas or NSSAs.  This would allow increasing the value of
  385.         ospfExtLsdbLimit in the remaining routers.
  386.  
  387.     o   Reevaluating the need to import certain external routes. If
  388.         ospfExtLsdbLimit cannot be increased, the network manager will
  389.         want to make sure that the more important routes continue to be
  390.         imported; this is accomplished by turning off the importing of
  391.  
  392.  
  393.  
  394. Moy                                                             [Page 7]
  395.  
  396. RFC 1765                 OSPF Database Overflow               March 1995
  397.  
  398.  
  399.         less important routes.
  400.  
  401. 5.  Operational experience
  402.  
  403.    The database overflow scheme described in this memo has been
  404.    implemented in the Proteon router for a number of years, with the
  405.    following differences. First, the router did not leave OverflowState
  406.    until it was restarted (i.e., ospfExitOverflowInterval was always 0).
  407.    Second, default AS-external-LSAs were not separated from non-default
  408.    AS-external-LSAs. Operationally the scheme performed as expected:
  409.    during overflow conditions, the routers converged on a common
  410.    database having less than a configured number of AS-external-LSAs.
  411.  
  412. 6.  Possible enhancements
  413.  
  414.    Possible enhancements to the overflow scheme include the following:
  415.  
  416.     o   Other LSA types, with the exception of the transit LSAs
  417.         (router-LSAs and network-LSAs), could be limited in a similar
  418.         fashion. For example, one could limit the number of summary-
  419.         LSAs, or group-membership-LSAs (see [6]).
  420.  
  421.     o   Rather than flushing all of its non-default AS-external-LSAs
  422.         when entering OverflowState, a router could flush a fixed number
  423.         whenever the database size hits ospfExtLsdbLimit. This would
  424.         allow the router to prioritize its AS-external-LSAs, flushing
  425.         the least important ones first.
  426.  
  427. A. Related MIB parameters
  428.  
  429.    The following OSPF MIB variables have been defined to support the
  430.    database overflow procedure described in this memo (see [4] for more
  431.    information):
  432.  
  433.     ospfExtLsdbLimit
  434.         As in Section 2.1 of this memo, the maximum number of non-
  435.         default AS-external-LSAs that can be stored within the database.
  436.         If set to -1, there is no limit.
  437.  
  438.     ospfExitOverflowInterval
  439.         As in Section 2.1 of this memo, the number of seconds that,
  440.         after entering OverflowState, a router will attempt to leave
  441.         OverflowState. This allows the router to again originate non-
  442.         default AS-external-LSAs.  When set to 0, the router will not
  443.         leave OverflowState until restarted.
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Moy                                                             [Page 8]
  451.  
  452. RFC 1765                 OSPF Database Overflow               March 1995
  453.  
  454.  
  455.     ospfLsdbOverflow
  456.         A trap indicating that the number of non-default AS-external-
  457.         LSAs has exceeded or equaled ospfExtLsdbLimit. In other words,
  458.         this trap indicates that the router is entering OverflowState.
  459.  
  460.     ospfLsdbApproachingOverflow
  461.         A trap indicating that the number of non-default AS-external-
  462.         LSAs has exceeded ninety percent of "ospfExtLsdbLimit".
  463.  
  464. References
  465.  
  466.    [1] Moy, J., "OSPF Version 2", RFC 1583, Proteon, Inc., March 1994.
  467.  
  468.    [2] Coltun, R., and V. Fuller, "The OSPF NSSA Option", RFC 1587,
  469.        RainbowBridge Communications, Stanford University, March 1994.
  470.  
  471.    [3] Moy, J., Editor, "OSPF Protocol Analysis", RFC 1245, Proteon,
  472.        Inc., July 1991.
  473.  
  474.    [4] Baker F., and R. Coltun, "OSPF Version 2 Management Information
  475.        Base", Work in Progress.
  476.  
  477.    [5] Moy, J., Editor, "Experience with the OSPF Protocol", RFC 1246,
  478.        Proteon, Inc., July 1991.
  479.  
  480.    [6] Moy, J., "Multicast Extensions to OSPF", RFC 1584, Proteon, Inc.,
  481.        March 1994.
  482.  
  483. Security Considerations
  484.  
  485.    Security issues are not discussed in this memo.
  486.  
  487. Author's Address
  488.  
  489.    John Moy
  490.    Cascade Communications Corp.
  491.    5 Carlisle Road
  492.    Westford, MA 01886
  493.  
  494.    Phone: 508-692-2600 Ext. 394
  495.    Fax:   508-692-9214
  496.    EMail: jmoy@casc.com
  497.  
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506. Moy                                                             [Page 9]
  507.  
  508.